package main

import (
	"fmt"
	"local/algorithm/util"
	"math"
)

type TreeNode = util.TreeNode

/**
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.


		 p
	   /   \
     p1     p2
    / \     / \
   p1l p1r p2l p2r

分治法

如果p==nil，深度为0
如果p!=nil，p1、p2都等于nil,那么深度为1
如果p!=nil,p1、p2中至少有一个不是叶子结点，那么深度为1+max(p1子树深度,p2子树深度)

*/

func main() {
	root := util.GenerateTreeLevel([]int{3, 9, 20, -1, -1, 15, 7})
	fmt.Println(maxDepth(root))
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	} else {
		return 1 + int(math.Max(float64(maxDepth(root.Left)), float64(maxDepth(root.Right))))
	}
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	} else {
		return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
